package lis

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"gitee.com/ljfirst/algo-go-sdk/tools"
	"strings"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/10 00:07
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 最长递增子序列 - 动态规划
 * */
type LIS_Dynamic struct {
	statistics []int
}

// grammar:字符串转数组，string转array :
// 1、arr := str[0:]
// 2、arr := []rune(str) // 这一种是 Unicode 字符，需要配合 arr[j]-'0' 才可以得到原来的数字
func (m *LIS_Dynamic) LISMethod(str string) int {
	if len(str) == 0 {
		return 0
	}
	//arr := str[0:]
	arr := []rune(str)
	m.statistics = make([]int, len(str), len(str))
	m.statistics[0] = 1
	for i := 1; i < len(arr); i++ {
		for j := 0; j < i; j++ {
			if arr[j]-'0' < arr[i]-'0' {
				m.statistics[i] = tools.Max(m.statistics[i], m.statistics[j]+1)
			}
		}
	}
	return m.statistics[len(m.statistics)-1]
}

func (m *LIS_Dynamic) LISStrMethod(str string) string {
	strLen := m.LISMethod(str)
	if strLen == 0 || len(m.statistics) == 0 {
		return ""
	}
	arr := str[0:]
	ans := make([]string, 0)
	trace := m.statistics[len(m.statistics)-1]
	for i := len(arr) - 1; i >= 0; i-- {
		if m.statistics[i] == trace {
			ans = append(ans, string(arr[i]))
			trace--
		}
	}
	sb := strings.Builder{} // grammar字符串数组转 字符串
	for i := len(ans) - 1; i >= 0; i-- {
		sb.WriteString(ans[i])
	}
	return sb.String()
}

func (m *LIS_Dynamic) GetAttribute() *C.Attribute {
	return &C.Attribute{
		Tags: []string{C.LIS, C.Dynamic},
		Desc: &C.Desc{
			Name:   "LIS_Dynamic",
			NameCn: "最长递增子序列:动态规划",
			Example: map[int]string{
			},
		},
	}
}
